package leetcode.hot100;

@SuppressWarnings("all")
public class _5_最长回文子串_扩展中心 {

    // "babad"的最长回文子串是"bab"或"aba"
    // "cbbd"的最长回文子串是"dd"
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return null;
        int start = 0;  //记录最长回文子串的起点
        int left = 0;   //记录最长回文子串的左边界
        int right = 0;  //记录最长回文子串的右边界
        int maxLen = 1; //保存当前最长回文子串的长度
        int i = 0;      //遍历指针
        char[] chars = s.toCharArray();
        while (i < chars.length) {
            // 将当前遍历到的字符视为中心点，向左右扩展找最长回文子串
            // 1.中心点左右相同的字符看作一个字符，并确定扩展的右边界起点
            right = i + 1;
            while (right < chars.length && chars[i] == chars[right]) {
                right++;
            }
            // 2.确定扩展的左边界起点
            left = i - 1;
            // 3.记录当前左边界起点，这将成为下一个中心扩展点的起点
            i = right;
            // 4.左右比较
            while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
                left--;
                right++;
            }
            // 5.得到当前最长回文子串的长度并更新子串起点
            int len = right - left - 1;
            if (len >= maxLen) {
                start = left + 1;
                maxLen = len;
            }
        }
        // 左闭右开
        return s.substring(start, start + maxLen);
    }

}
